package com.lwl.Algorithmic_data_structure.class04归并;


import com.lwl.Algorithmic_data_structure.归并排序.Code03_ReversePair;

/**
 * 给你一个数组，找出每个数中比他小且在他右边的数的个数（逆序对）
 * <p>
 * 思路：整体是基于归并排序的，因为在归并排序中每两个数之间的大小是确认的，而且比较过程是不回退的（nlogn）
 * 然后在归并操作上找出每次归并的两个数组之间存在的符合题意
 * 细节：因为注意下标边界问题
 */
public class Code03ReversePair {
    public static void main(String[] args) {
        // 1 2 2 4 5  ====  2 2 5 6 7
        System.out.println(reversePair(new int[]{1, 2, 2, 4, 5, 2, 2, 5, 6, 7}, 0, 9));
        int[] arr = {-2, 0};
        int q = reversePair(arr, 0, arr.length - 1);
        int j = Code03_ReversePair.reverPairNumber(arr);
        System.out.println(q);
        System.out.println(j);
        int testTime = 500000;
        int maxSize = 10;
        int maxValue = 10;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {

            int[] arr1 = Code03_ReversePair.generateRandomArray(maxSize, maxValue);
            int[] arr3 = Code03_ReversePair.copyArray(arr1);
//            for (int k : arr3) {
//                System.out.print(k + ",");
//            }
            int[] arr2 = Code03_ReversePair.copyArray(arr1);

            int ans1 = Code03_ReversePair.reverPairNumber(arr1);
            int ans2 = reversePair(arr2);
            if (ans1 != ans2) {
//            if (Code03_ReversePair.reverPairNumber(arr1) != Code03_ReversePair.comparator(arr2)) {
                System.out.println(ans1);
                System.out.println(ans2);
                break;
            }
        }
        System.out.println("测试结束");
    }

    public static int reversePair(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return 0;
        }
        return reversePair(arr, 0, arr.length - 1);
    }

    public static int reversePair(int[] arr, int l, int r) {
//        System.out.println("l : " + l + "r : " + r );
        if (l == r) {
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        int leftCount = reversePair(arr, l, mid);
        int rightCount = reversePair(arr, mid + 1, r);
        int curCount = merge(arr, l, mid, r);
        return leftCount + rightCount + curCount;
    }

    private static int merge(int[] arr, int l, int mid, int r) {
        int helpLen = r - l + 1;
        int[] help = new int[helpLen];
        int p1 = mid;
        int p2 = r;
        int helpIndex = helpLen - 1;
        int res = 0;
        while (p1 >= l && p2 >= mid + 1) {
            // 下面错误的例子，不能从小到大排！因为一旦p1的下标不动,p2右移时，此时ans进行累加是不对的
            //                  应该是只有在p1左移动时，ans进行累加才是正确的
            // 1 2 2 4 5 9 ====  2 2 5 6 7
            // ↑                ↑           p1:0,               p2:5
            //   ↑              ↑           p1:1,               p2:5           help : 1               逆序对 += p2(5) - (mid(4) + 1)
            //     ↑            ↑           p1:2,               p2:5           help : 1 2             逆序对 += p2(5) - (mid(4) + 1)
            //       ↑          ↑           p1:3,               p2:5           help : 1 2 2           逆序对 += p2(5) - (mid(4) + 1)   = 0
            //       ↑            ↑         p1:3,               p2:6           help : 1 2 2 2         逆序对 += p2(6) - (mid(4) + 1)   = 1
            //       ↑              ↑       p1:3,               p2:7           help : 1 2 2 2 2       逆序对 += p2(7) - (mid(4) + 1)   = 2
            //         ↑            ↑       p1:4,               p2:7           help : 1 2 2 2 2 4     逆序对 += p2(7) - (mid(4) + 1)   = 2
            //           ↑          ↑       p1:5(下次循环跳出),   p2:7           help : 1 2 2 2 2 4 5   逆序对 += p2(7) - (mid(4) + 1)   = 2
            // 相等的时候左边移动，因为相等移动右边的下标就会增加逆序对的数量
//            res += arr[p1] > arr[p2] ? p2 - (mid + 1) : 0;
//            help[helpIndex++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];

            res += arr[p1] > arr[p2] ? (p2 - mid) : 0;
            help[helpIndex--] = arr[p1] > arr[p2] ? arr[p1--] : arr[p2--];

        }
        while (p1 >= l) {
            help[helpIndex--] = arr[p1--];
        }
        while (p2 >= mid + 1) {
            help[helpIndex--] = arr[p2--];
        }
//        while (p1 <= mid) {
//            // 此时的左边全部大于右边，全都是逆序对
//            res += p2 - (mid + 1);
//            help[helpIndex++] = arr[p1++];
//        }
//        while (p2 <= r) {
//            help[helpIndex++] = arr[p2++];
//        }
        for (int i = 0; i < helpLen; i++) {
            arr[l + i] = help[i];
        }
        return res;
    }
}
